#include <bits/stdc++.h>

using namespace std;




struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//根据vector值构建二叉树
TreeNode * gou(vector<int> num){
    if(num.size()==0) return nullptr;
    TreeNode *root=new TreeNode(num[0]);
    queue<TreeNode*> s;
    s.push(root);
    int index=1,len=num.size();
    while(!s.empty()&&index<len){
        TreeNode *p=nullptr,*q=nullptr;
        p=new TreeNode(num[index++]);
        if(index<len) q=new TreeNode(num[index++]);
        TreeNode *r=s.front();s.pop();
        r->left=p;r->right=q;
        s.push(p),s.push(q);
    }
    return root;
}


class Solution1 {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> mp;
        mp.clear();
        int len=nums.size();
        for(int i=0;i<len;i++)
        {
            mp[nums[i]]++;
            if(mp[nums[i]]>len/2)
                return nums[i];
        }    
        return nums[0];
    }
};
class Solution2 {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};
class Solution{
public:
    //投票法
    int majorityElement(vector<int>& nums){
        int x=0,votes=0;
        for(auto num : nums){
            if(votes==0) x=num;
            votes+= (num==x?1:-1);
        }
        return x;
    }
};

int main(){
    vector<int> v={1, 2, 3, 2, 2, 2, 5, 4, 2};
    Solution s;
    cout << s.majorityElement(v) <<endl;


    return 0;
}